package com.hoppinzq.algorithm.graph;

import com.hoppinzq.algorithm.stackAndQueue.MyQueue;

/**
 * 6
 * 检测有向图的环
 */
public class DirectedCycle {
    private boolean[] marked;
    private boolean isCycle;
    private boolean[] onStack;

    public DirectedCycle(MyDigraph myDigraph){
        marked=new boolean[myDigraph.V()];
        onStack=new boolean[myDigraph.V()];
        isCycle=false;//没有环
        //所有顶点都要检测一遍是否有环（针对非连通图），若该顶点被检测过 marked=true，则不用检测了
        for(int v=0;v<myDigraph.V();v++){
            if(!marked[v]){
                dfs(myDigraph,v);
            }
        }
    }

    private void dfs(MyDigraph myDigraph,int v){
        marked[v]=true;
        onStack[v]=true;
        MyQueue<Integer> queue=myDigraph.getQueue(v);
        for (Integer i : queue) {
            if(!marked[i]){
                dfs(myDigraph,i);
            }
            if(onStack[i]){
                isCycle=true;
                return;
            }
        }
        onStack[v]=false;
    }

    public boolean isCycle(){
        return isCycle;
    }
}
